package com.hws.leetcode.Day_01_08;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * ClassName:leetcode_354
 * Package:com.hws.leetcode.Day_01_08
 * Description: 俄罗斯套娃信封问题
 *
 * @ date:2022/1/8 15:32
 * @ author:hws
 */
public class leetcode_354 {

    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
            }
        });
        List<Integer> secondList = new ArrayList<>();
        for (int i = 0; i < envelopes.length; i++) {
            secondList.add(envelopes[i][1]);
        }
        int[] dp = new int[envelopes.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i < secondList.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (secondList.get(i) > secondList.get(j)) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int num = 0;
        for (int i = 0; i < dp.length; i++) {
            num = Math.max(num, dp[i]);
        }
        return num;
    }

    public static void main(String[] args) {
        leetcode_354 lc = new leetcode_354();
        int[][] envelopes = new int[][]{{1, 1}, {1, 1}, {1, 1}, {1, 1}};
        System.out.println(lc.maxEnvelopes(envelopes));
    }

}
